package com.xiaoyu.backtracking;

import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;

/**
 * @program: DS_and_A
 * @description:
 * 给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 *
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 *
 * @author: YuWenYi
 * @create: 2021-05-26 10:08
 **/
public class LetterCombinations_17 {

    /*
    * 思路分析:
    * 1.组合中的所有情况的个数为:所有数字拥有的字符个数相乘
    * 例如"234" --> 就是3*3*3  --> 总共27种组合!
    * 2.注意是组合,因此"ad"和"da"属于同一个组合!
    * */
    public List<String> letterCombinations(String digits) {
        int len = digits.length();
        List<String> res = new ArrayList<>();
        if (len==0){
            return res;
        }
        //初始化
        HashMap<Character, String[]> map = new HashMap<>();
        map.put('2',new String[]{"a","b","c"});
        map.put('3',new String[]{"d","e","f"});
        map.put('4',new String[]{"g","h","i"});
        map.put('5',new String[]{"j","k","l"});
        map.put('6',new String[]{"m","n","o"});
        map.put('7',new String[]{"p","q","r","s"});
        map.put('8',new String[]{"t","u","v"});
        map.put('9',new String[]{"w","x","y","z"});

        StringBuilder path = new StringBuilder();
        int begin = 0;
        dfs(digits, len, begin, res, path, map);
        return res;
    }

    public void dfs(String digits,int len,int begin,List<String> res,StringBuilder path,HashMap<Character, String[]> map){
        //len多长,那么path就有多长,满足这个条件就能加进去了!
        if (path.length() == len){
            res.add(path.toString());
            return;
        }
        //for (int i = begin; i < digits.length(); i++) {
            //并不需要for循环,直接取begin中的字符串即可!
            String[] letters = map.get(digits.charAt(begin));
            for (String letter : letters) {
                path.append(letter);

                dfs(digits, len, begin + 1, res, path, map);

                path.deleteCharAt(path.length()-1);
            }
        //}
    }

    public static void main(String[] args) {
        LetterCombinations_17 letterCombinations17 = new LetterCombinations_17();
        List<String> list = letterCombinations17.letterCombinations("23");
        System.out.println(list);
    }
}
